{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ternary Expression Parser"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: parseTernary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三元表达式解析器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个表示任意嵌套三元表达式的字符串&nbsp;<code>expression</code>&nbsp;，求值并返回其结果。</p>\n",
    "\n",
    "<p>你可以总是假设给定的表达式是有效的，并且只包含数字，&nbsp;<code>'?'</code>&nbsp;，&nbsp;&nbsp;<code>':'</code>&nbsp;，&nbsp;&nbsp;<code>'T'</code>&nbsp;和 <code>'F'</code> ，其中 <code>'T'</code> 为真， <code>'F'</code> 为假。表达式中的所有数字都是 <strong>一位</strong> 数(即在 <strong>[0,9] </strong>范围内)。</p>\n",
    "\n",
    "<p>条件表达式从右到左分组(大多数语言中都是这样)，表达式的结果总是为数字 <code>'T'</code> 或 <code>'F'</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> expression = \"T?2:3\"\n",
    "<strong>输出：</strong> \"2\"\n",
    "<strong>解释：</strong> 如果条件为真，结果为 2；否则，结果为 3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> expression = \"F?1:T?4:5\"\n",
    "<strong>输出：</strong> \"4\"\n",
    "<strong>解释：</strong> 条件表达式自右向左结合。使用括号的话，相当于：\n",
    " \"(F ? 1 : (T ? 4 : 5))\" --&gt; \"(F ? 1 : 4)\" --&gt; \"4\"\n",
    "or \"(F ? 1 : (T ? 4 : 5))\" --&gt; \"(T ? 4 : 5)\" --&gt; \"4\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> expression = \"T?T?F:5:3\"\n",
    "<strong>输出：</strong> \"F\"\n",
    "<strong>解释：</strong> 条件表达式自右向左结合。使用括号的话，相当于：\n",
    "\"(T ? (T ? F : 5) : 3)\" --&gt; \"(T ? F : 3)\" --&gt; \"F\"\n",
    "\"(T ? (T ? F : 5) : 3)\" --&gt; \"(T ? F : 5)\" --&gt; \"F\"</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>5 &lt;= expression.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>expression</code>&nbsp;由数字,&nbsp;<code>'T'</code>,&nbsp;<code>'F'</code>,&nbsp;<code>'?'</code>&nbsp;和&nbsp;<code>':'</code>&nbsp;组成</li>\n",
    "\t<li><strong>保证&nbsp;</strong>了表达式是一个有效的三元表达式，并且每个数字都是 <strong>一位数</strong>&nbsp;</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ternary-expression-parser](https://leetcode.cn/problems/ternary-expression-parser/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ternary-expression-parser](https://leetcode.cn/problems/ternary-expression-parser/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"T?2:3\"', '\"F?1:T?4:5\"', '\"T?T?F:5:3\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stack = []\n",
    "        n = len(expression)\n",
    "        next_tf = False\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == '?':\n",
    "                next_tf = True\n",
    "            else:\n",
    "                if next_tf:\n",
    "                    if expression[i] == 'T':\n",
    "                        val = stack.pop()\n",
    "                        stack.pop()\n",
    "                        stack.append(val)\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                    next_tf = False\n",
    "                else:\n",
    "                    stack.append(expression[i])\n",
    "        return stack[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def parseTernary(self, expression: str) -> str:\n",
    "#         stack = []\n",
    "#         judge = True\n",
    "#         first = True\n",
    "#         for each in expression:\n",
    "#             if each == '?':\n",
    "#                 first = True\n",
    "#             elif each == ':':\n",
    "#                 first == False\n",
    "#             elif each.isdigit():\n",
    "#                 if first != judge:\n",
    "#                     continue\n",
    "#                 multi = multi * 10 + int(each)\n",
    "#             elif each == 'T':\n",
    "#                 judge = True\n",
    "#             elif each == 'F':\n",
    "#                 judge = False\n",
    "#             elif each == '(':\n",
    "#                 stack.append(each)\n",
    "#             elif each == ')':\n",
    "#                 temp = stack.pop()\n",
    "#                 while temp != '(':\n",
    "#                     temp = stack.pop()\n",
    "#                     if temp \n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        n = len(expression)\n",
    "        i = n - 1\n",
    "        stack = []\n",
    "        while i >= 0:\n",
    "            if expression[i].isalnum():\n",
    "                stack.append(expression[i])\n",
    "                i -= 1\n",
    "            elif expression[i] == ':':\n",
    "                i -= 1\n",
    "            elif expression[i] == '?':\n",
    "                i -= 1\n",
    "                left = stack.pop()\n",
    "                right = stack.pop()\n",
    "                if expression[i] == 'T':\n",
    "                    stack.append(left)\n",
    "                else:\n",
    "                    stack.append(right)\n",
    "                i -= 1\n",
    "        return stack.pop()\n",
    "\n",
    "# 作者：Funny Cori555\n",
    "# 链接：https://leetcode.cn/problems/ternary-expression-parser/solutions/2257716/san-yuan-biao-da-shi-jie-xi-by-funny-cor-wevd/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stark, srt = [], len(expression) - 1\n",
    "        while srt >= 0:\n",
    "            v = expression[srt]\n",
    "            if v == \"?\":\n",
    "                srt -= 1\n",
    "                a = expression[srt]\n",
    "                b = stark.pop()\n",
    "                if a == \"T\":\n",
    "                    stark.pop()\n",
    "                    stark.append(b)\n",
    "            elif v != \":\":\n",
    "                stark.append(v)\n",
    "            srt -= 1\n",
    "        return stark[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        n = len(expression)\n",
    "        st = []\n",
    "        i = n\n",
    "        while i > 0:\n",
    "            i -= 1\n",
    "            if expression[i] == '?':\n",
    "                st.pop(int(expression[i - 1] == 'T'))\n",
    "                i -= 1\n",
    "            elif expression[i] == ':':\n",
    "                continue\n",
    "            else:\n",
    "                st.insert(0, expression[i])\n",
    "        return st[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        res = []\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            # print(i)\n",
    "            if  res and res[-1]==\"?\":\n",
    "                wen = res.pop()\n",
    "                left = res.pop()\n",
    "                mao = res.pop()\n",
    "                right = res.pop()\n",
    "                if expression[i] == \"T\":\n",
    "                    res.append(left)\n",
    "                else:\n",
    "                    res.append(right)\n",
    "            else:\n",
    "                res.append(expression[i])\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "\n",
    "        stack = []\n",
    "        i = len(expression) - 1\n",
    "        while i >= 0:\n",
    "            ch = expression[i]\n",
    "            if ch.isalnum():\n",
    "                stack.append(ch)\n",
    "                i -= 1\n",
    "            elif ch == '?':\n",
    "                i -= 1\n",
    "                condition = expression[i]\n",
    "                left = stack.pop()\n",
    "                right = stack.pop()\n",
    "                if condition == 'T':\n",
    "                    stack.append(left)\n",
    "                else:\n",
    "                    stack.append(right)\n",
    "                i -= 1\n",
    "            else:\n",
    "                i -= 1\n",
    "        \n",
    "        return stack.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        is_con = False\n",
    "        stack = []\n",
    "        for i in range(len(expression) - 1, -1, -1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == \"?\":\n",
    "                is_con = True\n",
    "            else:\n",
    "                if is_con:\n",
    "                    if expression[i] == 'T':\n",
    "                        res = stack[-1]\n",
    "                        stack.pop()\n",
    "                        stack.pop()\n",
    "                        stack.append(res)\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                    is_con = False\n",
    "                else:\n",
    "                    stack.append(expression[i])\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        n=len(expression)\n",
    "        tenary=False\n",
    "        # stk只用来存储val\n",
    "        stk=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            # 如果遇到的是:\n",
    "            if expression[i]==':':\n",
    "                continue\n",
    "            # 如果遇到的是?\n",
    "            elif expression[i]=='?':\n",
    "                tenary=True\n",
    "            # 遇到了T/F/val\n",
    "            else:\n",
    "                # 遇到的是T/F?_:_中的T/F\n",
    "                if tenary:\n",
    "                    # 遇到的是T\n",
    "                    if expression[i]=='T':\n",
    "                        # 取出第一个val\n",
    "                        val=stk.pop()\n",
    "                        # 弹出F对应的val\n",
    "                        stk.pop()\n",
    "                        # 存入最后的val\n",
    "                        stk.append(val)\n",
    "                    # 遇到的是F\n",
    "                    else:\n",
    "                        # 弹出T对应的val，剩下的F对应的val就是最后的表达式\n",
    "                        stk.pop()\n",
    "                    tenary=False\n",
    "                # 遇到的是val\n",
    "                else:\n",
    "                    stk.append(expression[i])\n",
    "        return stk.pop()\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        lis,mark=[],False\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            if mark:\n",
    "                mark=False\n",
    "                continue\n",
    "            if expression[i]!=':' and expression[i]!='?':\n",
    "                lis.append(expression[i])\n",
    "            if expression[i]=='?':\n",
    "                mark=True\n",
    "                if expression[i-1]=='T':\n",
    "                    lis.pop(-2)\n",
    "                if expression[i-1]=='F':\n",
    "                    lis.pop(-1)\n",
    "        return lis[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stack = []\n",
    "        i=len(expression)-1\n",
    "        while(i>=0):\n",
    "            if expression[i].isalnum():\n",
    "                stack.append(expression[i])\n",
    "                i-=1\n",
    "            elif expression[i]=='?':\n",
    "                i-=1\n",
    "                left = stack.pop()\n",
    "                right = stack.pop()\n",
    "                if expression[i]=='T':\n",
    "                    stack.append(left)\n",
    "                else:\n",
    "                    stack.append(right)\n",
    "                i-=1\n",
    "            else:\n",
    "                i-=1\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        sta = []\n",
    "        n = len(expression)\n",
    "        while n>0:\n",
    "            n-=1\n",
    "            if expression[n]==\":\":continue\n",
    "            elif expression[n]==\"?\":\n",
    "                if expression[n-1]==\"T\":\n",
    "                    sta.pop(-2)\n",
    "                else:\n",
    "                    sta.pop()\n",
    "                n-=1\n",
    "            else: \n",
    "                sta.append(expression[n])\n",
    "        return sta[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        flags = 0\n",
    "        stk = []\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == '?':\n",
    "                flags = 1\n",
    "            else:\n",
    "                if flags:\n",
    "                    if expression[i] == 'T':\n",
    "                        res = stk[-1]\n",
    "                        stk.pop()\n",
    "                        stk.pop()\n",
    "                        stk.append(res)\n",
    "                    else:\n",
    "                        stk.pop()\n",
    "                    flags = 0\n",
    "                else:\n",
    "                    stk.append(expression[i])\n",
    "        return stk[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        is_condition = 0\n",
    "        stk = []\n",
    "        for i in range(len(expression) - 1, -1, -1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == '?':\n",
    "                is_condition = 1\n",
    "            else:\n",
    "                if is_condition:\n",
    "                    if expression[i] == 'T':\n",
    "                        res = stk[-1]\n",
    "                        stk.pop()\n",
    "\n",
    "                        stk.pop()\n",
    "                        stk.append(res)\n",
    "                    else:\n",
    "                        stk.pop()\n",
    "                    is_condition = 0\n",
    "                else:\n",
    "                    stk.append(expression[i])\n",
    "        return stk[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        is_con = False\n",
    "        stack = []\n",
    "        for i in range(len(expression) - 1, -1, -1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == \"?\":\n",
    "                is_con = True\n",
    "            else:\n",
    "                if is_con:\n",
    "                    if expression[i] == 'T':\n",
    "                        res = stack[-1]\n",
    "                        stack.pop()\n",
    "                        stack.pop()\n",
    "                        stack.append(res)\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                    is_con = False\n",
    "                else:\n",
    "                    stack.append(expression[i])\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def parseTernary(self, expression: str) -> str:\r\n",
    "        # 用来标记下一个遇到的字符是条件\r\n",
    "        is_condition = 0\r\n",
    "        stk = []\r\n",
    "        # 因为是从右至左结合,所以也从右至左遍历\r\n",
    "        for i in range(len(expression) - 1, -1, -1):\r\n",
    "            if expression[i] == ':':\r\n",
    "                continue\r\n",
    "            elif expression[i] == '?':  # 标记下一个遇到的字符是条件\r\n",
    "                is_condition = 1\r\n",
    "            else:\r\n",
    "                if is_condition:\r\n",
    "                    if expression[i] == 'T':  # 说明栈中的第一个元素是结果, 但要把错误结果删掉\r\n",
    "                        res = stk[-1]\r\n",
    "                        stk.pop()\r\n",
    "                        stk.pop()\r\n",
    "                        stk.append(res)\r\n",
    "                    else:  # 说明栈中第二个元素是结果, 删掉栈顶元素即可\r\n",
    "                        stk.pop()\r\n",
    "                    is_condition = 0\r\n",
    "                else:  # 当前扫描到的元素不是条件, 就是直接入栈\r\n",
    "                    stk.append(expression[i])\r\n",
    "        return stk[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        arr = list(expression)\n",
    "        stack = []\n",
    "        while arr:\n",
    "            is_sub = False\n",
    "            ele = arr.pop()\n",
    "            if ele == '?':\n",
    "                e1 = stack.pop()\n",
    "                e2 = stack.pop()\n",
    "                op = arr.pop()\n",
    "                if op == 'T':\n",
    "                    stack.append(e1)\n",
    "                else:\n",
    "                    stack.append(e2)\n",
    "            if ele not in ['?',':']:\n",
    "                stack.append(ele)\n",
    "        return stack[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        n = len(expression)\n",
    "\n",
    "        def compute(i, j):\n",
    "            if i == j:\n",
    "                return expression[i]\n",
    "            \n",
    "            left = i + 2\n",
    "            mid = -1\n",
    "            count = 0\n",
    "            for k in range(left + 1, j):\n",
    "                c = expression[k]\n",
    "                if c == '?':\n",
    "                    count -= 1\n",
    "                elif expression[k] == ':':\n",
    "                    count += 1\n",
    "                    if count == 1:\n",
    "                        mid = k\n",
    "                        break\n",
    "            if expression[i] == 'T':\n",
    "                return compute(left, mid - 1)\n",
    "            else:\n",
    "                return compute(mid + 1, j)\n",
    "\n",
    "        return compute(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        res = []\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            # print(i)\n",
    "            if  res and res[-1]==\"?\":\n",
    "                wen = res.pop()\n",
    "                left = res.pop()\n",
    "                mao = res.pop()\n",
    "                right = res.pop()\n",
    "                if expression[i] == \"T\":\n",
    "                    res.append(left)\n",
    "                else:\n",
    "                    res.append(right)\n",
    "            else:\n",
    "                res.append(expression[i])\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        l = len(expression)\n",
    "        i = l - 1\n",
    "        checklist = []\n",
    "        while i > -1:\n",
    "            if expression[i] != ':' and expression[i] != '?':\n",
    "                checklist.append(expression[i])\n",
    "            elif expression[i] == '?':\n",
    "                foreward = checklist.pop()\n",
    "                backward = checklist.pop()\n",
    "                if expression[i - 1] == 'F':\n",
    "                    checklist.append(backward)\n",
    "                else:\n",
    "                    checklist.append(foreward)\n",
    "                i -= 1\n",
    "            i -= 1\n",
    "        return checklist.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        expression=expression[::-1]\n",
    "        stak=[]\n",
    "        for t in (expression):\n",
    "            if len(stak)==0:\n",
    "                if t in 'TF?0123456789':\n",
    "                    stak.append(t)\n",
    "            else:\n",
    "                if stak[-1]==\"?\":\n",
    "                    # print(stak)\n",
    "                    stak.pop()#:\n",
    "                    a=stak.pop()\n",
    "                    b=stak.pop()\n",
    "                    c=t\n",
    "                    if c==\"T\":\n",
    "                        stak.append(a)\n",
    "                    elif c==\"F\":\n",
    "                        stak.append(b)\n",
    "                    \n",
    "                    # print(stak)\n",
    "                    # print(\"====\")\n",
    "                else:\n",
    "                    if t in 'TF?0123456789':\n",
    "                        stak.append(t) \n",
    "\n",
    "        print(stak)\n",
    "        \n",
    "        return stak[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stack = []\n",
    "\n",
    "        index = len(expression) - 1\n",
    "\n",
    "        stack.append(expression[index])\n",
    "\n",
    "        while index > 0:\n",
    "            index -= 1\n",
    "            if stack[-1] == \"?\":\n",
    "                stack.pop()\n",
    "                flag = expression[index]\n",
    "                left = stack.pop()\n",
    "                right = stack.pop()\n",
    "                if flag == \"T\":\n",
    "                    stack.append(left)\n",
    "                else:\n",
    "                    stack.append(right)\n",
    "            else:\n",
    "                stack.append(expression[index]) if expression[index] != \":\" else ...\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stark, srt = [], len(expression) - 1\n",
    "        while srt >= 0:\n",
    "            v = expression[srt]\n",
    "            if v == \"?\":\n",
    "                srt -= 1\n",
    "                b = stark.pop()\n",
    "                if expression[srt] == \"T\": stark[-1] = b\n",
    "            elif v != \":\": stark.append(v)\n",
    "            srt -= 1\n",
    "        return stark[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        level = 0\n",
    "        n = len(expression)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if expression[i] == '?':\n",
    "                level += 1\n",
    "            if expression[i] == ':':\n",
    "                level -= 1\n",
    "            if level == 0:\n",
    "                return self.parseTernary(expression[2:i]) if expression[0] == 'T' else self.parseTernary(expression[i+1:n])\n",
    "        return expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stack = []\n",
    "        label = 0\n",
    "        for i in range(len(expression)-1, -1, -1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == '?':\n",
    "                label = 1\n",
    "            else:\n",
    "                if label:\n",
    "                    if expression[i] == 'T':\n",
    "                        res = stack[-1]\n",
    "                        stack.pop()\n",
    "                        stack.pop()\n",
    "                        stack.append(res)\n",
    "                    elif expression[i] == 'F':\n",
    "                        stack.pop()\n",
    "                    label = 0\n",
    "                else:\n",
    "                    stack.append(expression[i])\n",
    "        return stack[-1]\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        from collections import deque\n",
    "        myStack = deque()\n",
    "        revExp = expression[::-1]\n",
    "        skip = False\n",
    "        for idx,s in enumerate(revExp):\n",
    "            # print(myStack)\n",
    "            if s == '?':\n",
    "                curBool = revExp[idx+1]\n",
    "                # print(curBool)\n",
    "                first, second = myStack.pop(), myStack.pop()\n",
    "                if curBool == 'T':\n",
    "                    myStack.append(first)\n",
    "                else:\n",
    "                    myStack.append(second)\n",
    "                skip = True\n",
    "            elif s == ':':\n",
    "                pass\n",
    "            elif s == 'T' or s == 'F':\n",
    "                if not skip:\n",
    "                    myStack.append(s)\n",
    "                skip = False\n",
    "            else:\n",
    "                myStack.append(s)\n",
    "        return myStack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        def evalExpression(if_condition, if_then, else_then):\n",
    "            if if_condition == \"T\":\n",
    "                return if_then\n",
    "            return else_then\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(expression)-1, -1, -1):\n",
    "            cur = expression[i]\n",
    "            if len(stack) > 0 and stack[-1] == \"?\":\n",
    "                question = stack.pop()\n",
    "                if_then = stack.pop()\n",
    "                colon = stack.pop()\n",
    "                else_then = stack.pop()\n",
    "                res = evalExpression(cur, if_then, else_then)\n",
    "                stack.append(res)\n",
    "            else:\n",
    "                stack.append(cur)\n",
    "        return stack[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stack = []\n",
    "        idx = len(expression) - 1\n",
    "        while idx >=0:\n",
    "            c = expression[idx]\n",
    "            idx -=1\n",
    "            if c==':':\n",
    "                continue\n",
    "            elif c=='?':\n",
    "                condition = expression[idx]\n",
    "                c1 = stack.pop()\n",
    "                c2 = stack.pop()\n",
    "                if condition=='T':\n",
    "                    stack.append(c1)\n",
    "                else:\n",
    "                    stack.append(c2)\n",
    "                idx -=1\n",
    "            else:\n",
    "                stack.append(c)\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        flag = 0\n",
    "        stk = []\n",
    "        # 从右向左遍历\n",
    "        for i in range(len(expression)-1, -1, -1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == '?':\n",
    "                flag = 1\n",
    "            else:\n",
    "                if flag:\n",
    "                    if expression[i] == 'T':\n",
    "                        tmp = stk[-1]\n",
    "                        stk.pop()\n",
    "                        stk.pop()\n",
    "                        stk.append(tmp)\n",
    "                    else:\n",
    "                        stk.pop()\n",
    "                    flag = 0\n",
    "                else:\n",
    "                    stk.append(expression[i])\n",
    "        \n",
    "        return stk[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        is_condition = 0\n",
    "        stack = []\n",
    "        for i in range(len(expression) - 1, -1, -1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == '?':\n",
    "                is_condition = 1\n",
    "            else:\n",
    "                if is_condition:\n",
    "                    if expression[i] == 'T':\n",
    "                        res = stack[-1]\n",
    "                        stack.pop()\n",
    "                        stack.pop()\n",
    "                        stack.append(res)\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                    is_condition = 0\n",
    "                else:\n",
    "                    stack.append(expression[i])\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        val_stack = []\n",
    "\n",
    "        idx = len(expression) - 1\n",
    "        \n",
    "        while idx >= 0:\n",
    "            if idx == len(expression) - 1:\n",
    "                val_stack.append(expression[idx])\n",
    "            elif expression[idx] == '?' or expression[idx] == ':':\n",
    "                pass\n",
    "            elif expression[idx + 1] == '?':\n",
    "                pre_val = val_stack.pop()\n",
    "                next_val = val_stack.pop()\n",
    "                if expression[idx] == 'T':\n",
    "                    val = pre_val\n",
    "                else:\n",
    "                    val = next_val\n",
    "                val_stack.append(val)\n",
    "            else:\n",
    "                val_stack.append(expression[idx])\n",
    "            idx -= 1\n",
    "        \n",
    "        return val_stack[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        while len(expression)!=1:\n",
    "            for i in range(len(expression)-1,-1,-1):\n",
    "                if expression[i]=='?':\n",
    "                    break\n",
    "            if expression[i-1]=='T':\n",
    "                temp=expression[i+1]\n",
    "            else:\n",
    "                temp=expression[i+3]\n",
    "            expression=expression[:i-1]+temp+expression[i+4:]\n",
    "        return expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "\n",
    "        # 用栈的话，从右往左处理比较方便\n",
    "\n",
    "        def dfs(expr: str) -> str:\n",
    "            if len(expr) == 1:\n",
    "                return expr\n",
    "\n",
    "            for i, c in enumerate(expr):\n",
    "                if c != 'T' and c != 'F':\n",
    "                    continue\n",
    "                \n",
    "                j = i + 1\n",
    "                level = 0\n",
    "                while j < len(expr):\n",
    "                    if expr[j] == '?':\n",
    "                        level += 1\n",
    "                    if expr[j] == ':':\n",
    "                        level -= 1\n",
    "\n",
    "                    if level == 0:\n",
    "                        if c == 'T':\n",
    "                            return dfs(expr[i+2:j])\n",
    "                        return dfs(expr[j+1:])\n",
    "                    j += 1\n",
    "            return expr\n",
    "        \n",
    "        return dfs(expression)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        is_condition = 0\n",
    "        stack = []\n",
    "        for i in range(len(expression) - 1, -1, -1):\n",
    "            if expression[i] == ':':\n",
    "                continue\n",
    "            elif expression[i] == '?':\n",
    "                is_condition = 1\n",
    "            else:\n",
    "                if is_condition:\n",
    "                    if expression[i] == 'T':\n",
    "                        res = stack[-1]\n",
    "                        stack.pop()\n",
    "                        stack.pop()\n",
    "                        stack.append(res)\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                    is_condition = 0\n",
    "                else:\n",
    "                    stack.append(expression[i])\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stack = []\n",
    "        n = len(expression)\n",
    "        i = n-1\n",
    "        while i >= 0:\n",
    "            c = expression[i]\n",
    "            if not stack or c.isdigit():\n",
    "                stack.append(c)\n",
    "                i -= 1\n",
    "            elif c == '?':\n",
    "                if expression[i-1] == 'T':\n",
    "                    num = stack.pop()\n",
    "                    stack.pop()\n",
    "                    stack.append(num)\n",
    "                elif expression[i-1] == 'F':\n",
    "                    stack.pop()\n",
    "                i -= 2\n",
    "            elif c == ':':\n",
    "                stack.append(expression[i-1])\n",
    "                i -= 2\n",
    "            # print(stack)\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stk = []\n",
    "        is_condition = 0\n",
    "        for i in range(len(expression)-1, -1, -1):\n",
    "            if expression[i] == \":\":\n",
    "                continue\n",
    "            elif expression[i] == \"?\":\n",
    "                is_condition = 1\n",
    "            else:\n",
    "                if is_condition:\n",
    "                    if expression[i] == \"T\":\n",
    "                        res = stk[-1]\n",
    "                        stk.pop()\n",
    "                        stk.pop()\n",
    "                        stk.append(res)\n",
    "                    else:\n",
    "                        stk.pop()\n",
    "                    is_condition = 0\n",
    "                    \n",
    "                else:\n",
    "                    stk.append(expression[i])\n",
    "\n",
    "        return stk[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        #直观想法是递归\n",
    "        if len(expression)==1:\n",
    "            return expression[0]\n",
    "        #递归的精髓是怎么找当前问号对应的冒号(或者说是哪一个冒号)\n",
    "        #计数遍历即可吧(需要保证问号与冒号是同一层次的,再递归地划分子问题)\n",
    "        pre,cur,j=1,0,0\n",
    "        for i in range(2,len(expression)):\n",
    "            if expression[i]==\"?\":\n",
    "                pre+=1\n",
    "            elif expression[i]==\":\":\n",
    "                cur+=1\n",
    "                if cur==pre:\n",
    "                    j=i\n",
    "                    break\n",
    "        if expression[0]==\"T\":\n",
    "            return self.parseTernary(expression[2:j])\n",
    "        else:\n",
    "            return self.parseTernary(expression[j+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        lis,mark=[],False\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            if mark:\n",
    "                mark=False\n",
    "                continue\n",
    "            if expression[i]!=':' and expression[i]!='?':\n",
    "                lis.append(expression[i])\n",
    "            if expression[i]=='?':\n",
    "                mark=True\n",
    "                if expression[i-1]=='T':\n",
    "                    lis.pop(-2)\n",
    "                if expression[i-1]=='F':\n",
    "                    lis.pop(-1)\n",
    "        return lis[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        lis,mark=[],False\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            if mark:\n",
    "                mark=False\n",
    "                continue\n",
    "            if expression[i]!=':' and expression[i]!='?':\n",
    "                lis.append(expression[i])\n",
    "            if expression[i]=='?':\n",
    "                mark=True\n",
    "                if expression[i-1]=='T':\n",
    "                    lis.pop(-2)\n",
    "                if expression[i-1]=='F':\n",
    "                    lis.pop(-1)\n",
    "        return lis[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stack, q = [], [*expression]\n",
    "        while q:\n",
    "            c = q.pop()\n",
    "            if c == '?':\n",
    "                stack[-2:] = stack[-1-(q.pop()=='F')],\n",
    "            elif c != ':':\n",
    "                stack.append(c)\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        lis,mark=[],False\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            if mark:\n",
    "                mark=False\n",
    "                continue\n",
    "            if expression[i]!=':' and expression[i]!='?':\n",
    "                lis.append(expression[i])\n",
    "            if expression[i]=='?':\n",
    "                mark=True\n",
    "                if expression[i-1]=='T':\n",
    "                    lis.pop(-2)\n",
    "                if expression[i-1]=='F':\n",
    "                    lis.pop(-1)\n",
    "        return lis[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        lis,mark=[],False\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            if mark:\n",
    "                mark=False\n",
    "                continue\n",
    "            if expression[i]!=':' and expression[i]!='?':\n",
    "                lis.append(expression[i])\n",
    "            if expression[i]=='?':\n",
    "                mark=True\n",
    "                if expression[i-1]=='T':\n",
    "                    lis.pop(-2)\n",
    "                if expression[i-1]=='F':\n",
    "                    lis.pop(-1)\n",
    "        return lis[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        def single(sub_expression: str) -> str:\n",
    "            if sub_expression[0] == 'T':\n",
    "                return sub_expression[2]\n",
    "            elif sub_expression[0] ==\"F\":\n",
    "                return sub_expression[-1]\n",
    "        \n",
    "        while '?' in expression:\n",
    "            # print(expression)\n",
    "            for i in range(len(expression)-1,-1,-1):\n",
    "                if expression[i] == '?':\n",
    "                    sub = expression[i-1:i+4]\n",
    "                    print(sub)\n",
    "                    sub_res = single(sub)\n",
    "                    print(sub_res)\n",
    "                    expression = expression[0:i-1] + sub_res + expression[i+4:]\n",
    "                    break\n",
    "        return expression\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        #直观想法是递归\n",
    "        if len(expression)==1:\n",
    "            return expression[0]\n",
    "        #递归的精髓是怎么找当前问号对应的冒号(或者说是哪一个冒号)\n",
    "        #计数遍历即可吧(需要保证问号与冒号是同一层次的,再递归地划分子问题)\n",
    "        pre,cur,j=1,0,0\n",
    "        for i in range(2,len(expression)):\n",
    "            if expression[i]==\"?\":\n",
    "                pre+=1\n",
    "            elif expression[i]==\":\":\n",
    "                cur+=1\n",
    "                if cur==pre:\n",
    "                    j=i\n",
    "                    break\n",
    "        if expression[0]==\"T\":\n",
    "            return self.parseTernary(expression[2:j])\n",
    "        else:\n",
    "            return self.parseTernary(expression[j+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        #直观想法是递归\n",
    "        if len(expression)==1:\n",
    "            return expression[0]\n",
    "        #递归的精髓是怎么找当前问号对应的冒号(或者说是哪一个冒号)\n",
    "        #计数遍历即可吧\n",
    "        pre,cur,j=1,0,0\n",
    "        for i in range(2,len(expression)):\n",
    "            if expression[i]==\"?\":\n",
    "                pre+=1\n",
    "            elif expression[i]==\":\":\n",
    "                cur+=1\n",
    "                if cur==pre:\n",
    "                    j=i\n",
    "                    break\n",
    "        if expression[0]==\"T\":\n",
    "            return self.parseTernary(expression[2:j])\n",
    "        else:\n",
    "            return self.parseTernary(expression[j+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        st = []\n",
    "        n = len(expression)\n",
    "        p = n-1\n",
    "        while p >=0 :\n",
    "            if expression[p] != \"?\":\n",
    "                st = [expression[p]] + st\n",
    "                p-=1\n",
    "            else:\n",
    "                p-=1\n",
    "                other = \"\"\n",
    "                if len(st) > 3:\n",
    "                    other = \"\".join(st[3:])\n",
    "\n",
    "                if expression[p] == 'T':\n",
    "                    expression = expression[:p] + st[0] + other\n",
    "                    p = len(expression) -1\n",
    "                else:\n",
    "                    expression = expression[:p] + st[2] + other\n",
    "                    p = len(expression) -1\n",
    "                st = []\n",
    "        #print(expression)\n",
    "        return expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseTernary(self, expression: str) -> str:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < len(expression):\n",
    "            if expression[i] in ['T', 'F'] and i < len(expression) - 1 and expression[i+1] == '?':\n",
    "                stack.append(expression[i])\n",
    "                i += 2\n",
    "            elif expression[i] == ':':\n",
    "                stack.append(':')\n",
    "                i += 1\n",
    "            else:\n",
    "                res = expression[i]\n",
    "                while len(stack) > 0 and stack[-1] == ':':\n",
    "                    res = stack[-2] if stack[-3] == 'T' else res\n",
    "                    stack = stack[:-3]\n",
    "                stack.append(res)\n",
    "                i += 1\n",
    "\n",
    "        return stack[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
